package main

import "fmt"

func quickSort(arr []int, start, end int) {
	if start < end {
		i, j := start, end
		key := arr[(start+end)/2]
		for arr[i] < key {
			i++
		}
		for arr[j] > key {
			j--
		}
		// 这里先把那些已经符合条件的过滤掉

		if i <= j {
			arr[i], arr[j] = arr[j], arr[i]
			i++
			j--
		}

		//  !递归：

		// 如果 两指针没有重合，将会继续向中间缩小
		if start < j {
			// 左边的继续来一波快排
			quickSort(arr, start, j)
		}
		if end > i {
			// 右边的继续来一波快排

			quickSort(arr, i, end)
		}

	}
}

func main() {

	arr := []int{3, 7, 9, 8, 38, 93, 12, 222, 45, 93, 23, 84, 65, 2}
	quickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

